package com.duoduo.链表;

import com.duoduo.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 两数相加2
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * 示例 2：
 *
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * 示例 3：
 *
 * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 * 输出：[8,9,9,9,0,0,0,1]
 * @author: chaidl  ！
 * @create: 2022-05-10 23:19
 */
public class 两数相加2 {
	public static void main(String[] args) {
		ListNode l1=new ListNode(2);
		ListNode l2=new ListNode(4);
		ListNode l3=new ListNode(3);
		l1.next=l2;
		l2.next=l3;
		ListNode l4=new ListNode(5);
		ListNode l5=new ListNode(6);
		ListNode l6=new ListNode(4);
		l4.next=l5;
		l5.next=l6;
		addTwoNumbers(l1,l4);
	}
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		Deque<Integer> stack1=new LinkedList<>();
		Deque<Integer> stack2=new LinkedList<>();
		ListNode result=null;
		while (l1!=null){
			stack1.push(l1.val);
			l1=l1.next;
		}
		while (l2!=null){
			stack2.push(l2.val);
			l2=l2.next;
		}
		int carry=0;
		while (!stack1.isEmpty() || ! stack2.isEmpty() || carry!=0){
			carry+=stack1.isEmpty()?0:stack1.pop();
			carry+=stack2.isEmpty()?0:stack2.pop();
			ListNode tmp=new ListNode(carry%10);
			carry/=10;
			tmp.next=result;
			result=tmp;
		}
		return result;
	}
}
